package ToYesterday.Day1002_Offer03;

import org.junit.Test;

import java.util.HashSet;

public class SearchSameNum {

    HashSet<Integer> set = new HashSet<>();

    @Test
    public void TestDemo(){
        int[] nums = {0,1,2,3,4,5,6,7,12,9,10,11,12};
        //solution_1(nums);//使用排序方法
        //solution_2(nums);//使用hashset方法
        //solution_3(nums);//使用O(1)的方法
        solution_4(nums);//不修改原本数组的方法
    }

    public void solution_4(int[] num){
        System.out.println(useNoSpace(num));
    }

    private int useNoSpace(int[] nums) {
        int begin = 0;
        int stop = nums.length-1;
        int mid =0;
        while (begin<stop){
            mid = (begin+(stop-begin)/2);
            if (getCount(nums,begin,mid)>(mid-begin+1)){
                stop = mid;
            }else if(getCount(nums,mid+1,stop)>(stop-mid)){
                begin=mid+1;
            }
        }
        return begin;
    }

    public int getCount(int[] nums,int start,int stop){
        int numSum=0;
        for (int i = 0;i<nums.length;i++){
            if (nums[i]>=start&&nums[i]<=stop)
                numSum++;
        }

        return numSum;
    }

    public void solution_3(int[] num){
        System.out.println(useKeng(num));
    }
    public int useKeng(int[] num){
        for (int i =0;i<num.length;i++){
            while (num[i]!=i&&num[i]!=num[num[i]]){

                int temp = num[i];
                num[i] = num[temp];
                num[temp] = temp;
            }
            if (num[i]==num[num[i]])return num[i];
        }
        return 0;



    }

    public void solution_2(int[] num){
        System.out.println(useHashTable(num));
    }
    public int useHashTable(int [] nums){
        for (int i = 0;i<nums.length;i++){
            if (!set.contains(nums[i])){
                set.add(nums[i]);
            }else return nums[i];

        }

        return 0;
    }


    public void solution_1(int[] num){
        searchSameNum(num);
    }
    public int searchSameNum(int[] num){
        sort(num,0,num.length-1);
        for (int i = 0;i<num.length;i++){
            if (num[i]==num[i+1])return num[i];
        }
        return 0;
    }

    public void sort(int[] num,int start,int stop){
        if (start == stop)return;
        int midd = start+(stop-start)/2;
        sort(num,start,midd);
        sort(num,midd+1,stop);
        merge(num,start,midd,stop);
    }
    public void merge(int[] num,int start, int midd, int stop){
        int[] newnum = new int[stop-start+1];
        int k= 0;
        int pstart = start;
        int pstop = stop;
        int mid=midd;
        while (start<=mid&&(midd+1)<=stop){
            if (num[start]<num[midd+1]){
                newnum[k] = num[start];
                k++;start++;
            }else {
                newnum[k] = num[midd+1];
                k++;midd++;
            }
        }

        while (start<=mid){
            newnum[k] = num[start];
            start++;k++;
        }
        while ((midd+1)<=stop){
            newnum[k] = num[midd+1];
            midd++;
            k++;
        }
        k=0;
        for (int i = pstart;i<=pstop;i++ ){
            num[i]=newnum[k];
            k++;
        }

    }
}
